package newBee.class2;

import common.ArrayQueue;
import common.ArrayUtils;

/**
 * 计算公式：
 * m = n-k+1：可以计算出获得最大值的数组容积
 * [6, 5, 4, 3, 5, 6]
 */
public class TestDemo {

    public static void main(String[] args) {
        int[] arr = {6, 5, 4, 3, 5, 7};
        int k = 3;
        int[] ans = maxSlidingWindow(arr, k);
        ArrayUtils.printArr(ans);
    }

    // 单调队列
    public static int[] maxSlidingWindow(int[] arr, int k) {
        int h = 0, t = 0, n = arr.length;
        int[] deque = new int[n];

        for (int i = 0; i < k - 1; i++) {
            while (h < t && arr[deque[t - 1]] <= arr[i]) {
                t--;
            }
            deque[t++] = i;
        }
        int[] ans = new int[n - k + 1];
        int l = 0, r = k - 1;
        for (; r < n; r++, l++) {
            while (h < t && arr[deque[t - 1]] <= arr[r]) {
                t--;
            }
            deque[t++] = r;
            ans[l] = arr[deque[h]];
            if(deque[h]==l){
                h++;
            }
        }
        return ans;
    }
}
